import unittest
from alg import Solution
from gen import generate_test_cases


class TestCanJump(unittest.TestCase):
    def test_example_cases(self):
        sol = Solution()
        test_cases = [
            ([2, 3, 1, 1, 4], True),
            ([3, 2, 1, 0, 4], False),
            ([0], True),
            ([2, 0, 0], True),
            ([1, 1, 1, 0], True)
        ]

        for nums, expected in test_cases:
            result = sol.canJump(nums)
            print(f"测试用例: {nums}, 预期结果: {expected}, 实际结果: {result}")
            self.assertEqual(result, expected)

    def test_generated_cases(self):
        sol = Solution()
        test_cases = generate_test_cases(5, n_range=(5, 15))

        for nums in test_cases:
            expected = self.brute_force_can_jump(nums)
            result = sol.canJump(nums)
            print(f"随机测试用例: {nums}, 预期结果: {expected}, 实际结果: {result}")
            self.assertEqual(result, expected)

    def brute_force_can_jump(self, nums):
        n = len(nums)
        if n <= 1:
            return True

        dp = [False] * n
        dp[-1] = True

        for i in range(n - 2, -1, -1):
            for j in range(1, nums[i] + 1):
                if i + j < n and dp[i + j]:
                    dp[i] = True
                    break

        return dp[0]


if __name__ == '__main__':
    unittest.main(verbosity=2) 